package com.justnow.offer;

/**
 * @author justnow
 * Created on 2020-09-05
 * Description
 *
 * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
 *
 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
 */
public class Solution21 {
    public TreeNode sortedArrayToBST01(int[] nums) {
        return helper(nums, 0, nums.length - 1);
        //return helper2(nums, 0, nums.length - 1);
        //return helper3(nums, 0, nums.length - 1);

    }

    /**
     * 方法一，中序遍历，总是选择中间位置左边的数字作为根节点
     * @param nums
     * @param left
     * @param right
     * @return
     */
    public TreeNode helper(int[] nums, int left, int right) {
        if (left < right) {
            return null;
        }

        // 总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;

    }

    /**
     * 方法二，总是选择中间位置右边的数字作为根节点
     * @param nums
     * @param left
     * @param right
     * @return
     */
    public TreeNode helper2(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        // 总是选择中间位置右边的数字作为根节点
        int mid = (left + right + 1) / 2;
        TreeNode root = new TreeNode(mid);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }



}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int x) {
        this.val = x;
    }
}
